#include <iostream>
#include <assert.h>
#include <string>
#include <vector>

using namespace std;

template<class K> struct BSTreeNode 
{
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;
    K _data;

    BSTreeNode(const K& data)
        :_left(nullptr)
         ,_right(nullptr)
         ,_data(data)
    {}
};

template<class K> class BSTree
{
    typedef BSTreeNode<K> Node;
public:
    bool insert(const K& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            return true;
        }

        Node* cur = _root;
        Node* parent = nullptr;

        while (cur)
        {
            if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_data < data)
            {
                parent = cur;
                cur = cur->_right;
            }
            else return false;
        }
        
        cur = new Node(data);
        if (parent->_data < data)
            parent->_right = cur;
        else 
            parent->_left = cur;

        return true;
    }

    bool erase(const K& data)
    {
        
    }

    Node* find(const K& data)
    {
        if (_root == nullptr)
            return nullptr;


    }

    bool empty() const { return _root == nullptr; }

    void InOrder() { _InOrder(_root); cout << endl; }
    ~BSTree() { _Destroy(_root); }

public:

    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_data << ' ';
        _InOrder(root->_right);
    }

    void _Destroy(Node* root)
    {
        if (root == nullptr)
            return;

        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }

private:
    Node* _root = nullptr;
};
